home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / graphic / rtnews.zip / RTNV2N8 < prev    next >
Text File  |  1992-09-13  |  19KB  |  347 lines
  1.  _ __                 ______                         _ __
  2. ' )  )                  /                           ' )  )
  3.  /--' __.  __  ,     --/ __  __.  _. o ____  _,      /  / _  , , , _
  4. /  \_(_/|_/ (_/_    (_/ / (_(_/|_(__<_/ / <_(_)_    /  (_</_(_(_/_/_)_
  5.              /                               /|
  6.             '                               |/
  7.  
  8.             "Light Makes Right"
  9.  
  10.             October 27, 1989
  11.                 Volume 2, Number 8
  12.  
  13. Compiled by Eric Haines, 3D/Eye Inc, 2359 Triphammer Rd, Ithaca, NY 14850
  14.     NOTE ADDRESS CHANGE: wrath.cs.cornell.edu!eye!erich
  15.     [distributed by Michael Cohen <m-cohen@cs.utah.edu>, but send
  16.     contributions and subscriptions requests to Eric Haines]
  17. All contents are US copyright (c) 1989 by the individual authors
  18. Archive locations: anonymous FTP at cs.uoregon.edu (128.223.4.1) and at
  19.            freedom.graphics.cornell.edu (128.84.247.85), /pub/RTNews
  20.  
  21. Contents:
  22.     Introduction
  23.     Tracing Tricks, edited by Eric Haines
  24.  
  25. -------------------------------------------------------------------------------
  26.  
  27. Introduction
  28.  
  29.     I've decided to pass on an article published in the SIGGRAPH '89
  30. "Introduction to Ray Tracing" course notes.  It's something of a "best of the
  31. Ray Tracing News" compendium of ideas.  Since the notes are not easy for
  32. everyone to access, and the article probably will not be printed elsewhere, I
  33. thought it worthwhile to reprint here.
  34.  
  35. -------------------------------------------------------------------------------
  36.  
  37. Tracing Tricks, edited by Eric Haines
  38.  
  39. Over the years I have learnt a variety of tricks to increase the performance
  40. and image quality of my ray tracer.  It's almost a cliche that today's
  41. successful trick is tomorrow's established technique.  Photorealistic computer
  42. graphics is, after all, concerned with figuring out shortcuts and
  43. approximations for rendering various physical phenomena, i.e. tricks.
  44.  
  45. For whatever reason, many of the tricks mentioned here are not common
  46. knowledge.  Some have been published (and sometimes overlooked), some have
  47. been discussed informally and have never made it into research papers, and
  48. others seem to have appeared out of nowhere.  It's most likely that there are
  49. tricks that are commonly known that have not percolated over to me yet.
  50.  
  51. When possible, I have tried to give appropriate references or attributions; if
  52. not attributed, the ideas are my own (I think!).  My apologies if I have
  53. overlooked anyone.  Only references that do not appear in the book's "Ray
  54. Tracing Bibliography" are included at the end of this article.  For more
  55. general rendering hacks, see [Whitted85], which originally inspired me to
  56. attempt to pass on some ideas from my bag of tricks.
  57.  
  58.  
  59. Ambient Light
  60.  
  61. One common trick (origins unknown) is to put a light at the eye to do better
  62. ambient lighting.  Normally if a surface is lit by only ambient light, its
  63. shading is pretty crummy.  For example, a non-reflective cube totally in
  64. shadow will have all of its faces shaded the exact same shade.  All edges
  65. disappear and the cube becomes a hexagonal blob.  The light at the eye gives
  66. the cube definition.  Note that a light at the eye does not need shadow
  67. testing:  wherever the eye can see, the light can see, and vice versa.
  68. However, this trick can lead to various artifacts, e.g.  there will always be
  69. a highlight near the center of every specular sphere in the image.
  70.  
  71.  
  72. Efficiency Schemes
  73.  
  74. There are any number of efficiency schemes out there, including Bounding
  75. Volume Hierarchy, Octree, Grid, and 5D Ray Classification.  See Jim Arvo's
  76. section of the book for an excellent overview of all of these.  The most
  77. important conclusion is that any efficiency scheme is better than none.  Even
  78. on the simplest scenes an efficiency scheme will help execution.  For example,
  79. in one test scene with only ten objects, using an efficiency scheme made the
  80. job take only one third the time.  Grid subdivision is probably the quickest
  81. to implement, though the others are not that much harder.
  82.  
  83. While at the University of Utah, John Peterson and Tom Malley actually
  84. implemented Whitted/Rubin, Kay/Kajiya, and an octree scheme, and found that
  85. all three schemes were within 10-20% of each other speedwise.  In an informal
  86. survey at SIGGRAPH '88, the BV Hierarchy, Octree, Grid and 5D schemes all had
  87. about the same number of users (all the 5D users were from Apollo; on the
  88. other hand, 5D is the new kid on the block).
  89.  
  90. There are a number of techniques I have found to be generally useful for all
  91. efficiency schemes.
  92.  
  93. 1) When shadow testing, keep the opaque object (if any) which shadowed each
  94.    light for each ray tree node.  Try this object immediately during the next
  95.    shadow test at that ray tree node.  Odds are that whatever shadowed your
  96.    last intersection point will shadow again.  If the object is hit you can
  97.    immediately stop testing because the light is not seen.  This was first
  98.    published in [Haines86].
  99.  
  100. 2) When shadow testing, save transparent objects for later intersection.  Only
  101.    if no opaque object is hit should the transparent objects be tested.  The
  102.    idea here is to avoid doing work on transparent filters when in fact the
  103.    light does not reach the surface.
  104.  
  105. 3) Don't calculate the normal for each intersection.  Get the normal only
  106.    after all intersection calculations are done and the closest object for
  107.    each node is known.  After all, each ray can have only one intersection
  108.    point and one normal.  Saving intermediate results is worthwhile for some
  109.    intersection calculations, which are then used if the object is actually
  110.    hit.  This idea was first mentioned in [Whitted85].  Similarly, other
  111.    calculations about the surface can be delayed, such as (u,v) location, etc.
  112.  
  113. 4) One other idea (which I have not tested) is sorting each intersection list
  114.    by various criteria.  Most efficiency schemes have in common the idea of
  115.    lists of objects to be tested.  For a given list, the order of testing is
  116.    important.  For example, all else being equal, if a list contained a spline
  117.    surface and a polygon, I would want to test the polygon first since it is
  118.    usually a quicker intersection test.  Given an opaque object and a bounding
  119.    box in a list, I probably want to test the opaque object first when doing
  120.    shadow testing, since I want to find any intersection as soon as possible.
  121.    If two polygons are on the list, I probably want to test the larger one
  122.    first, as it is more likely to cast a shadow or give me a maximum depth
  123.    (see next section).  There are many variations on this theme and at this
  124.    point little work has been done on these possibilities.
  125.  
  126.  
  127. Bounding Volume Hierarchy
  128.  
  129. I have a strong bias towards this scheme since it handles a wide variety of
  130. object sizes, types, and orientations in a robust fashion.  Other schemes will
  131. often be faster, but this scheme has the fewest crippling pathological cases
  132. (e.g. a grid subdivision scheme is useless whenever most of the objects fall
  133. into one grid box).  I favor the automatic bounding volume generation technique
  134. described by [Goldsmith87].
  135.  
  136. I have found a number of tricks to speed up hierarchy traversal, most of which
  137. are simple to implement. Some of the ideas can also be useful for other
  138. efficiency schemes.
  139.  
  140. 1) Keep track of the closest intersection distance.  Whenever an object is
  141.    hit, keep its distance as the maximum distance to search.  During further
  142.    intersection testing use this distance to cut short the intersection
  143.    calculations:  if an object or bounding box is beyond the maximum distance,
  144.    no further testing of it needs to be done.  Note that for shadow testing
  145.    the distance to the light provides an initial maximum.
  146.  
  147. 2) When building a ray intersection tree, keep the ray tree which was
  148.    previously built.  For each ray tree node, intersect the object in the old
  149.    ray tree, then proceed to intersect the bounding box/object tree.  By
  150.    intersecting the old object first you can usually obtain a good maximum
  151.    distance immediately, which can then be used to aid trick #1.
  152.  
  153. 3) When shooting rays fr